package LC;

/**
 * https://leetcode.com/problems/trapping-rain-water/description/
 * Given n non-negative integers representing an elevation map
 * where the width of each bar is 1,
 * compute how much water it is able to trap after raining.
 * For example,
 * Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
 */
public class LC_042_TrappingRainWater_TwoPointers {
    public static void main(String[] args) {
        int[] a = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        int n = Solution.trap(a);
        System.out.println(n);
    }

    static class Solution {
        static int trap(int[] height) {
            int length;
            int maxLeftHeight = 0, maxRightHeight = 0;
            int result = 0;
            int temp;

            if (height == null || (length = height.length) == 0)
                return 0;

            int[] leftMaxHeight = new int[length];
            int[] rightMaxHeight = new int[length];

            for (int i = 0; i < length; i++) {
                leftMaxHeight[i] = maxLeftHeight;
                maxLeftHeight = Math.max(maxLeftHeight, height[i]);
            }

            for (int i = length - 1; i >= 0; i--) {
                rightMaxHeight[i] = maxRightHeight;
                maxRightHeight = Math.max(maxRightHeight, height[i]);
            }

            for (int i = 0; i < length; i++) {
                temp = Math.min(leftMaxHeight[i], rightMaxHeight[i]);
                if (temp >= height[i])
                    result += temp - height[i];
            }
            return result;
        }
    }

    static class Solution_2 {
        static int trap(int[] height) {
            int n = height.length;
            int res = 0;
            int l = 0, r = n - 1;

            while (l < r) {
                int minh = Math.min(height[l], height[r]);
                if (height[l] == minh) {
                    while (++l < r && height[l] < minh)
                        res += minh - height[l];
                } else {
                    while (l < --r && height[r] < minh)
                        res += minh - height[r];
                }
            }

            return res;
        }
    }
}
